/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author zhongfang
 *
 */
public class BrickWall {
    public static int leastBricks(List<List<Integer>> wall) {
        HashMap<Integer,Integer> freq=new HashMap<>();
        for(List<Integer> list:wall){
            int sum=0;
            for(int i=0;i<list.size()-1;i++){
                sum+=list.get(i);
                list.set(i,sum);
                int count=1;
                if(freq.containsKey(sum)){
                    count=freq.get(sum)+1;
                }
                freq.put(sum,count);
            }
        }
        int maxFreq=-1;
        int maxX=0;
        for(Map.Entry<Integer,Integer> ent:freq.entrySet()){
            if(maxFreq<ent.getValue()){
                maxFreq=ent.getValue();
                maxX=ent.getKey();
            }
        }
        int result=0;
        for(List<Integer> list:wall){
        	int indx=Collections.binarySearch(list,maxX);
            if(indx<0||indx==list.size()-1){//不包含,在最后一个，是长度而不是位置
                result++;
            }
        }
        return result;
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] tmp={{1,2,2,1},{3,1,2},{1,3,2},{2,4},{3,1,2},{1,3,1,1}};
		List<List<Integer>> wall=new ArrayList<>(tmp.length);
		for (int[] is : tmp) {
			ArrayList<Integer> integers=new ArrayList<>(is.length);
			for (int i : is) {
				integers.add(i);
			}
			wall.add(integers);
		}
		System.out.println(leastBricks(wall));
	}

}
